package com.hqq.exercise.array;

/**
 * CountOfK 数字在排序数组中出现的次数
 * 题目描述:
 * 统计一个数字在排序数组中出现的次数
 * 样例输入:
 * {1,2,3,3,3,3,3,4,5},3
 * 样例输出:
 * 4
 * 思路:
 * 1.使用二分查找找出第一个K和最后一个K
 * Created by heqianqian on 2017/8/22.
 */
public class CountOfK {

    public static int countOfK(int[] array, int num) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == num) {
                count++;
            }
        }
        return count;
    }

    public static int countOfK2(int[] array, int num) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int startIndex = 0;
        int endIndex = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == num) {
                startIndex = i;
                break;
            }
        }
        for (int i = array.length - 1; i >= 0; i--) {
            if (array[i] == num) {
                endIndex = i;
                break;
            }
        }
        return (startIndex == 0 && endIndex == 0) ? 0 : (endIndex - startIndex + 1);
    }

    public static int countOfKBiChop(int[] array, int num) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int startIndex = getStartIndex(array, num, 0, array.length - 1);
        int endIndex = getEndIndex(array, num, 0, array.length - 1);

        if (startIndex >= 0 && endIndex >= 0 && endIndex >= startIndex) {
            return endIndex - startIndex + 1;
        }
        return 0;
    }

    /**
     * 获得最后一个K在数组中的下标
     */
    private static int getEndIndex(int[] array, int num, int start, int end) {
        if (start > end) {
            return -1;
        }

        int middleIndex = (end + start) / 2;
        int middleData = array[middleIndex];

        if (middleData == num) {//中间元素为k

            if ((middleIndex < array.length - 1) && (array[middleIndex + 1] != num) || middleIndex == array.length - 1) {
                return middleIndex;
            } else {
                start = middleIndex + 1;
            }
        } else if (middleData > num) {
            end = middleIndex - 1;
        } else {
            start = middleIndex + 1;
        }
        return getEndIndex(array, num, start, end);
    }

    /**
     * 获得第一个K在数组的坐标
     */

    private static int getStartIndex(int[] array, int num, int start, int end) {
        if (start > end) {
            return -1;
        }
        int middleIndex = (start + end) / 2;
        int middleData = array[middleIndex];

        if (middleData == num) {//中间元素为k
            if (((middleIndex > 0) && (array[middleIndex - 1] != num)) || middleIndex == 0) {
                /*当前元素为K 且前一个元素不是K*/
                return middleIndex;
            } else {
                end = middleIndex - 1;
            }
        } else if (middleData > num) {
            end = middleIndex - 1;
        } else {
            start = middleIndex + 1;
        }
        return getStartIndex(array, num, start, end);
    }

}
